The present invention relates to linear feedback shift register pseudorandom number generators. More particularly, the present invention relates to such pseudorandom number generators having a reduced number of storage devices.
Pseudorandom numbers have many desirable properties and enjoy wide use. Due to their randomness, pseudorandom numbers serve as good noise emulators that provide assistance in digital system testing and measurement, data scrambling, coding, cryptography, and signal modulation. An effective way to perform a comprehensive test and verification of a system is to feed the system with a pseudorandom number generator running in real time. In such a setup, the pseudorandom number generator derives its clock signal from the system and outputs a k-bit random sample every clock cycle. Each random sample consists of k concatenated random bits of either 1 or 0. The pseudorandom samples closely resemble white noise which may be used to exercise and check data buses, registers, memory devices, signal processing functions in the system, etc. This approach greatly facilitates system debug and functional verification down to the bit level.
It is therefore desirable to have an inexpensive and effective way of generating pseudorandom numbers.
One apparatus presently used for generating k-bit pseudorandom numbers using k linear feedback shift registers (LFSRs) is described in U.S. Pat. No. 4,965,881 issued to Dilley on Mar. 27, 1990. The Dilley apparatus implements an n'th order generating polynomial using an m-stage LFSR (i.e., m storage devices), where n.noteq.m, that produces a k-bit random word, where k=m, per clock cycle. One particular embodiment in accordance with a 7.sup.th order generating polynomial f(x)=1=x.sup.6 +x.sup.7 is shown in FIG. 1. As shown, Dilley's embodiment requires 16 storage devices to produce a 16-bit pseudorandom word per clock cycle. The Dilley apparatus also comprises 17 modulo-2 adders 12 to produce a 16-bit word. Moreover, Dilley presented a method of determining how to couple the storage devices 11 and the modulo-2 adders 12 to output lines 10. The method presented included creating a matrix having dimensions k.times.k (e.g., 16.times.16 in FIG. 1) that described the iterative generation of a k-bit pseudorandom word. Storage devices, modulo-2 adders and hardware to perform operations on the matrix all cost money. Therefore the design complexity and cost of a pseudorandom number generator as described by Dilley increases as the size of the word to be produced increases.
A need therefore exists for an apparatus that will provide k-bit pseudorandom words employing fewer than k storage devices, k+1 modulo-2 adders and hardware to accommodate a k.times.k dimension matrix indicative of how to couple the adders and storage devices to output lines.